/*
    * Copyright (C) 2007 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License");
    * you may not use this file except in compliance with the License.
    * You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.google.common.collect;
  
  import static com.google.common.base.Preconditions.checkArgument;
  import static com.google.common.base.Preconditions.checkNotNull;
  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
  import static com.google.common.collect.CollectPreconditions.checkRemove;
  
  import com.google.common.annotations.GwtCompatible;
  import com.google.common.annotations.GwtIncompatible;
  import com.google.common.primitives.Ints;
  
  import java.io.InvalidObjectException;
  import java.io.ObjectStreamException;
  import java.io.Serializable;
  import java.util.ConcurrentModificationException;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.Set;
  
  import javax.annotation.Nullable;
  
  /**
   * Basic implementation of {@code Multiset<E>} backed by an instance of {@code
   * Map<E, Count>}.
   *
   * <p>For serialization to work, the subclass must specify explicit {@code
   * readObject} and {@code writeObject} methods.
   *
   * @author Kevin Bourrillion
   */
  @GwtCompatible(emulated = true)
  abstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E>
      implements Serializable {
  
    private transient Map<E, Count> backingMap;
  
    /*
     * Cache the size for efficiency. Using a long lets us avoid the need for
     * overflow checking and ensures that size() will function correctly even if
     * the multiset had once been larger than Integer.MAX_VALUE.
     */
    private transient long size;
  
    /** Standard constructor. */
    protected AbstractMapBasedMultiset(Map<E, Count> backingMap) {
      this.backingMap = checkNotNull(backingMap);
      this.size = super.size();
    }
  
    /** Used during deserialization only. The backing map must be empty. */
    void setBackingMap(Map<E, Count> backingMap) {
      this.backingMap = backingMap;
    }
  
    // Required Implementations
  
    /**
     * {@inheritDoc}
     *
     * <p>Invoking {@link Multiset.Entry#getCount} on an entry in the returned
     * set always returns the current count of that element in the multiset, as
     * opposed to the count at the time the entry was retrieved.
     */
    @Override
    public Set<Multiset.Entry<E>> entrySet() {
      return super.entrySet();
    }
  
    @Override
    Iterator<Entry<E>> entryIterator() {
      final Iterator<Map.Entry<E, Count>> backingEntries =
          backingMap.entrySet().iterator();
      return new Iterator<Multiset.Entry<E>>() {
        Map.Entry<E, Count> toRemove;
  
        @Override
        public boolean hasNext() {
          return backingEntries.hasNext();
        }
  
        @Override
        public Multiset.Entry<E> next() {
          final Map.Entry<E, Count> mapEntry = backingEntries.next();
         toRemove = mapEntry;
         return new Multisets.AbstractEntry<E>() {
           @Override
           public E getElement() {
             return mapEntry.getKey();
           }
           @Override
           public int getCount() {
             Count count = mapEntry.getValue();
             if (count == null || count.get() == 0) {
               Count frequency = backingMap.get(getElement());
               if (frequency != null) {
                 return frequency.get();
               }
             }
             return (count == null) ? 0 : count.get();
           }
         };
       }
 
       @Override
       public void remove() {
         checkRemove(toRemove != null);
         size -= toRemove.getValue().getAndSet(0);
         backingEntries.remove();
         toRemove = null;
       }
     };
   }
 
   @Override
   public void clear() {
     for (Count frequency : backingMap.values()) {
       frequency.set(0);
     }
     backingMap.clear();
     size = 0L;
   }
 
   @Override
   int distinctElements() {
     return backingMap.size();
   }
 
   // Optimizations - Query Operations
 
   @Override public int size() {
     return Ints.saturatedCast(size);
   }
 
   @Override public Iterator<E> iterator() {
     return new MapBasedMultisetIterator();
   }
 
   /*
    * Not subclassing AbstractMultiset$MultisetIterator because next() needs to
    * retrieve the Map.Entry<E, Count> entry, which can then be used for
    * a more efficient remove() call.
    */
   private class MapBasedMultisetIterator implements Iterator<E> {
     final Iterator<Map.Entry<E, Count>> entryIterator;
     Map.Entry<E, Count> currentEntry;
     int occurrencesLeft;
     boolean canRemove;
 
     MapBasedMultisetIterator() {
       this.entryIterator = backingMap.entrySet().iterator();
     }
 
     @Override
     public boolean hasNext() {
       return occurrencesLeft > 0 || entryIterator.hasNext();
     }
 
     @Override
     public E next() {
       if (occurrencesLeft == 0) {
         currentEntry = entryIterator.next();
         occurrencesLeft = currentEntry.getValue().get();
       }
       occurrencesLeft--;
       canRemove = true;
       return currentEntry.getKey();
     }
 
     @Override
     public void remove() {
       checkRemove(canRemove);
       int frequency = currentEntry.getValue().get();
       if (frequency <= 0) {
         throw new ConcurrentModificationException();
       }
       if (currentEntry.getValue().addAndGet(-1) == 0) {
         entryIterator.remove();
       }
       size--;
       canRemove = false;
     }
   }
 
   @Override public int count(@Nullable Object element) {
     Count frequency = Maps.safeGet(backingMap, element);
     return (frequency == null) ? 0 : frequency.get();
   }
 
   // Optional Operations - Modification Operations
 
   /**
    * {@inheritDoc}
    *
    * @throws IllegalArgumentException if the call would result in more than
    *     {@link Integer#MAX_VALUE} occurrences of {@code element} in this
    *     multiset.
    */
   @Override public int add(@Nullable E element, int occurrences) {
     if (occurrences == 0) {
       return count(element);
     }
     checkArgument(
         occurrences > 0, "occurrences cannot be negative: %s", occurrences);
     Count frequency = backingMap.get(element);
     int oldCount;
     if (frequency == null) {
       oldCount = 0;
       backingMap.put(element, new Count(occurrences));
     } else {
       oldCount = frequency.get();
       long newCount = (long) oldCount + (long) occurrences;
       checkArgument(newCount <= Integer.MAX_VALUE,
           "too many occurrences: %s", newCount);
       frequency.getAndAdd(occurrences);
     }
     size += occurrences;
     return oldCount;
   }
 
   @Override public int remove(@Nullable Object element, int occurrences) {
     if (occurrences == 0) {
       return count(element);
     }
     checkArgument(
         occurrences > 0, "occurrences cannot be negative: %s", occurrences);
     Count frequency = backingMap.get(element);
     if (frequency == null) {
       return 0;
     }
 
     int oldCount = frequency.get();
 
     int numberRemoved;
     if (oldCount > occurrences) {
       numberRemoved = occurrences;
     } else {
       numberRemoved = oldCount;
       backingMap.remove(element);
     }
 
     frequency.addAndGet(-numberRemoved);
     size -= numberRemoved;
     return oldCount;
   }
 
   // Roughly a 33% performance improvement over AbstractMultiset.setCount().
   @Override public int setCount(@Nullable E element, int count) {
     checkNonnegative(count, "count");
 
     Count existingCounter;
     int oldCount;
     if (count == 0) {
       existingCounter = backingMap.remove(element);
       oldCount = getAndSet(existingCounter, count);
     } else {
       existingCounter = backingMap.get(element);
       oldCount = getAndSet(existingCounter, count);
 
       if (existingCounter == null) {
         backingMap.put(element, new Count(count));
       }
     }
 
     size += (count - oldCount);
     return oldCount;
   }
 
   private static int getAndSet(Count i, int count) {
     if (i == null) {
       return 0;
     }
 
     return i.getAndSet(count);
   }
 
   // Don't allow default serialization.
   @GwtIncompatible("java.io.ObjectStreamException")
   @SuppressWarnings("unused") // actually used during deserialization
   private void readObjectNoData() throws ObjectStreamException {
     throw new InvalidObjectException("Stream data required");
   }
 
   @GwtIncompatible("not needed in emulated source.")
   private static final long serialVersionUID = -2250766705698539974L;
 }